package test.h0820;

import java.util.*;

/**
 * @author 不知名帅哥
 * @version 1.0
 * @description 猜密码
 * @date 2024/8/20 22:25
 */
public class Main6 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int[] nums = Arrays.stream(sc.nextLine().split(",")).mapToInt(Integer::parseInt).toArray();
        int k = Integer.parseInt(sc.nextLine());
        getRes(nums, k);
    }

    private static void getRes(int[] nums, int k) {
        List<LinkedList<Integer>> ans = new ArrayList<>();
        LinkedList<Integer> temp = new LinkedList<>();
        boolean[] used = new boolean[nums.length];

        Arrays.sort(nums); //事先按照字典序排序
        backTrack(ans, temp, 0, nums, k, used);
        System.out.println(ans);
    }

    private static void backTrack(List<LinkedList<Integer>> ans, LinkedList<Integer> temp, int start, int[] nums, int k, boolean[] used) {
        if (temp.size() >= k) {
            ans.add(new LinkedList<>(temp));
        }

        //是在判断当前路径temp和剩余元素组合起来是否还能满足长度为k的组合。如果当前路径的长度加上剩余未使用的元素个数仍然小于k，
        // 那么继续递归下去也无法得到一个长度为k的组合，所以直接返回，避免无效的递归。
        if (temp.size() + (nums.length - start) < k) return;

        for (int i = start; i < nums.length; i++) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            temp.addLast(nums[i]);
            backTrack(ans, temp, i + 1, nums, k, used);
            temp.removeLast(); //回溯
        }
    }
}
